package Search_07;

/*
 * @Author 罗
 * @date 2020/3/18 - 11:20 下午
 *
 */

import Sort_06.MergeSorting_07;

import java.lang.reflect.Array;
import java.util.Arrays;

public class BinarySearch_02 {


    public static void main(String[] args) {

        int[] array = {4, 8, 23, 56, 1, 100, 100, 100, 100, 1, 1, 11, 1, 7, 7, 7, 3};
        int find = 7;
        MergeSorting_07.mergeSorting(array, 0, array.length - 1, new int[array.length]);
        int index = binarySearch(array, 0, array.length, find);
        System.out.println(Arrays.toString(array) + "\n" + find + "索引是" + index);

        int[] resultIndex = binarySearchAll(array, 0, array.length, 100);

        System.out.println(Arrays.toString(resultIndex));
    }

    /**
     * 二分查找算法
     *
     * @param array
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int binarySearch(int[] array, int left, int right, int findValue) {
        /*
         * 先确定该数组的中间下标
         * */
        int mid = (left + right) / 2;
        /*
         * 将要查找的数和中间值比较
         *   有可能right == left 就是要查找的那个数
         * */
        if (left > right) {
            /*
             * 递归完成，但是没有找到findValue
             * */
            return -1;
        }
        if (findValue > array[mid]) {
            /*
             * 要查找的值大于mid对应的元素
             * 要查找的值在mid索引的右边
             * */
            return binarySearch(array, mid + 1, right, findValue);
        } else if (findValue < array[mid]) {
            /*
             * 要查找的值在索引的左边
             * */
            return binarySearch(array, left, mid - 1, findValue);
        } else {
            /*
             * 找到了
             * */
            return mid;
        }

    }

    /**
     * 当一个数组中，有多个相同的值时，将所有的值都找到
     *
     * @param array
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int[] binarySearchAll(int[] array, int left, int right, int findValue) {

        if (left > right) {
            return new int[]{-1};
        }

        int midIndex = (left + right) / 2;
        if (findValue > array[midIndex]) {
            return binarySearchAll(array, midIndex + 1, right, findValue);
        } else if (findValue < array[midIndex]) {
            return binarySearchAll(array, left, midIndex - 1, findValue);
        } else {
            /*
             * 向左、右扫描的时候，可以排除自身，提升效率
             * */
            int midLeft = midIndex - 1;
            int midRight = midIndex + 1;
            /*
             * 找到索引不急着返回
             * 先向左查询相同的值
             *      范围判断要在前，短路与，后面就不会越界了
             * */
            while (midLeft >= 0 && findValue == array[midLeft]) {
                midLeft--;
            }
            /*
             * 向右查询相同的值
             * */
            while (midRight < array.length && findValue == array[midRight]) {
                midRight++;
            }
            /*
             * while循环之后，会往左、右 各自多移一位
             * 左边往左多移了一位，因此向右移一位，+1
             * */
            midLeft++;
            /*
             * 右边向右多移了一位，因此向左移一位， -1
             * */
            midRight--;
            /*
             * 长度 = 范围 + 1;
             * */
            int[] resultIndex = new int[midRight - midLeft + 1];
            for (int i = 0; i < resultIndex.length; i++) {
                resultIndex[i] = midLeft;
                midLeft++;
            }
            return resultIndex;
        }

    }
}
